package oj;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class LC118 {
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> retList=new ArrayList<>();
        //组装特殊的第一行和第二行
        List<Integer> first=new ArrayList<>();
        //组装第一行
        first.add(1);
        retList.add(first);
        if(numRows==1){
            return retList;
        }
        //组装第二行[1,1]
        List<Integer> sec=new ArrayList<>();
        sec.add(1);
        sec.add(1);
        retList.add(sec);
        if(numRows==2){
           return retList;
        }
       //此时numrows至少三行
        for(int i=3;i<=numRows;i++){
            List<Integer> prev=retList.get(i-1-1);
            List<Integer> cur=new ArrayList<>();
            cur.add(1);
            for (int j = 2; j <i ; j++) {
                int tmpValue= prev.get(j-1-1)+prev.get(j-1);
                cur.add(tmpValue);
            }
            cur.add(1);
            retList.add(cur);
        }
        return retList;
    }
}
